1533. Генерация анаграмм

Напишите программу, которая генерирует все возможные слова из заданного набора букв.

Например, из слова “abc” в результате перестановки букв можно получить слова “abc”, “acb”, “bac”, “bca”, “cab” и “cba”.

Входные слова могут содержать повторяющиеся буквы. Программа должна исключать повторный вывод одного и того же слова. Все слова следует выводить по возрастанию в алфавитном порядке.

Вход. Первая строка содержит количество тестов. Каждая следующая строка содержит одно слово из букв латинского алфавита (от A до Z). Буквы верхнего и нижнего регистра считаются различными.

Выход. Для каждого теста выведите все возможные уникальные слова, которые можно составить из заданных букв, в порядке возрастания. Каждое слово следует выводить в отдельной строке. Буквы верхнего регистра в алфавитном порядке считаются меньшими, чем соответствующие буквы нижнего регистра.

Пример входа	Пример выхода
3 aAb abc acba	Aab Aba aAb abA bAa baA abc acb bac bca cab cba aabc aacb abac abca acab acba baac baca bcaa caab caba cbaa

РЕШЕНИЕ

комбинаторика - генерация перестановок

Упражнение

1. Чем отличается лексикографическая сортировка слов от алфавитной?

2. Рассмотрим строку “zAZaaZ”. Укажите порядок букв при алфавитной и лексикографической сортировке.

3. С помощью какой функции STL можно реализовать генерацию всех перестановок букв в слове?

4. Функция sort по умолчанию сортирует буквы в слове в лексикографическом порядке. Как с ее помощью реализовать алфавитную сортировку?

5. Реализуйте функцию алфавитной сортировки int lt(char a, char b), которая передается в качестве третьего аргумента функции sort.

6. Как найти алфавитно наименьшую перестановку букв строки s?

Анализ алгоритма

Сначала отсортируем символы входной строки по возрастанию в соответствии с алфавитным порядком. Далее будем использовать встроенную функцию next_permutation для генерации всех перестановок.

Так как стандартная (лексикографическая) сортировка предполагает, что любая буква верхнего регистра меньше любой буквы нижнего регистра, необходимо определить собственную функцию сравнения символов. Например, при стандартной сортировке для букв a, A, z, Z, r, R результатом будет “ARZarz”. Однако в задаче требуется сортировка и генерация перестановок в алфавитном порядке AaBbCc…Zz. Поэтому из букв a, A, z, Z, r, R необходимо получить строку “AaRrZz”.

Пример

В первом тесте для строки “aAb” наименьшей перестановкой будет “Aab”, а наибольшей “baA”.

Реализация алгоритма

Функция lt используется для сортировки символов и генерации перестановок. Она сравнивает два символа в соответствии с алфавитным порядком AaBbCc…Zz.

int lt(char a, char b)

{

if (toupper(a) != toupper(b)) return (toupper(a) < toupper(b));

return (a < b);

}

Основная часть программы. Читаем количество тестов n.

cin >> n;

Последовательно обрабатываем n тестов.

for (i = 0; i < n; i++)

{

Читаем входную строку s и сортируем ее символы в алфавитном порядке.

cin >> s;

sort(s.begin(), s.end(), lt);

Выводим текущую анаграмму (перестановку символов) и с помощью функции next_permutation генерируем следующую, пока это возможно.

do {

cout << s << endl;

} while (next_permutation(s.begin(), s.end(), lt));

}